package medium;

import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2022/4/16 16:29
 */
public class No81_搜索旋转排序数组II {
    public static void main(String[] args) {
        Solution81 solution81 = new Solution81();
        int[] nums = new int[]{4,0,4,4,4,4};
        boolean search = solution81.search(nums, 0);
        System.out.println(search);
    }
}

class Solution81 {
     public boolean search(int[] nums, int target) {
         //二分查找,有重复元素的二分查找
         //定义头尾中间
         //头
         int red = 0;
         //尾
         int green = nums.length - 1;
         while (red <= green) {
             //中间
             int yellow = (red + green) / 2;
             //找非降序区间
             if (nums[red] == target || nums[green] == target || nums[yellow] == target) {
                 return true;
             } else if (nums[red] == nums[yellow] || nums[yellow] == nums[green]) {
                 //无法确定非降序,则废弃
                 //不能无脑废弃,如果nums[green]==target,则GG
                 green--;
                 red++;
                 continue;
             }

             if (nums[red] <= nums[yellow]) {
                 //并不能确定非降序,所以在上面处理让它是非降序
                 //经过上面处理 red-yellow已经非降序
                 if (target > nums[red] && target < nums[yellow]) {
                     green = yellow - 1;
                 } else {
                     red = yellow + 1;
                 }
             } else {
                 //说明red-yellow 乱序,则 yellow-green非降序
                 if (target > nums[yellow] && target < nums[green]) {
                     red = yellow + 1;
                 } else {
                     green = yellow - 1;
                 } 
             } 
         }
         return false;
    }
}



    //public boolean search(int[] nums, int target) {
    //    //1,1,2,2,3,4,5,6,6
    //    //5,6,6,1,1,2,2,3,4
    //    
    //    //二分查找
    //    //先去重
    //    Set<Integer> set = new HashSet<>();
    //    for (int num : nums) {
    //        set.add(num);
    //    }
    //    
    //    //扔list,排序即可
    //    List<Integer> list = new ArrayList<>();
    //    for (int setNum : set) {
    //        list.add(setNum);
    //    }
    //    //排序
    //    list.sort(new Comparator<Integer>() {
    //        @Override
    //        public int compare(Integer o1, Integer o2) {
    //            return o1 > o2 ? 1 : -1;
    //        }
    //    });
    //    
    //    //1,2,3,4...
    //    //开始二分查找
    //    int red = 0;
    //    int green = list.size() - 1;
    //    while (red <= green) {
    //        int mid = (red + green) / 2;
    //        if (target < list.get(mid)) {
    //            green = mid - 1;
    //        } else if (target > list.get(mid)) {
    //            red = mid + 1;
    //        } else {
    //            return true;
    //        } 
    //    }
    //    return false;
    //}


